package com.bee.剑指offer;

/**
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 *
 * f(n) = f(n - 1) + f(n - 2) + ... + f(1)
 * 同理：f(n - 1) = f(n - 2) + f(n - 3) + ... + f(1)
 * 所以，将公式 1 中的f(n - 2) + f(n - 3) + ... + f(1)替换为f(n - 1)。
 * 公式 1 变为：f(n) = f(n - 1) + f(n - 1) = f(n - 1) * 2 （公式 3）
 * 同理：f(n - 1) = f(n - 2) + f(n - 2) = f(n - 2) * 2（公式 4）
 * 结合公式 3 和公式 4: f(n) = f(n - 2) * 2 * 2。因此可以推出：f(n) = 2^(n - 1)
 *
 * @version 1.0.0
 * @Author yong.Mr
 * @data 2021-03-13
 */
public class 跳台阶扩展 {

    public static int jumpFloorII(int target) {
        if (target <= 1) {
            return 1;
        }
        return 1 << target - 1;
    }

    public static void main(String[] args) {

        int number = 20;
        System.out.println(number<<3);  // number*2^3    number<<3(中的3代表是2^3多少次方，次方数)
        System.out.println(number>>3);  // number/2^3
        System.out.println(jumpFloorII(3));
        System.out.println(Math.pow(2,5));

    }
}
